public class Solution {
    public static List<Integer> grayCode(int n) {
        if(n == 0) {
            List<Integer> list = new ArrayList<>();
            list.add(0);
            return list;
        }
        List<Integer> tmp = grayCode(n - 1);
        int addN = 1 << (n - 1);
        List<Integer> r = new ArrayList<>(tmp);
        for(int i = tmp.size() - 1; i >= 0; i--) {
            r.add(addN + tmp.get(i));
        }
        return r;
    }
}